package bin_tree.oj;

import java.util.HashMap;
import java.util.Map;

public class Num106 {
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int[] preOrderImage = reverse(inorder,postorder);
        return buildTreeInternal(preOrderImage,inorder,0,inorder.length);
    }
    int index = 0;
    private TreeNode buildTreeInternal(int[] preOrderImage, int[] inOrder, int left, int right) {
        if(left >= right){
            return null;
        }
        if (index > preOrderImage.length){
            return null;
        }
        TreeNode root = new TreeNode(preOrderImage[index]);
        index++;
        int pos = map.get(root.val);
        root.right = buildTreeInternal(preOrderImage,inOrder,pos+1,right);
        root.left = buildTreeInternal(preOrderImage,inOrder,left,pos);
        return root;
    }

    private int[] reverse(int[] inorder, int[] postorder) {
        int[] ret = new int[postorder.length];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = postorder[ret.length - 1 - i];
        }
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return ret;
    }
}
